package mergeSort;

public class MergeSort {

	public static void main(String[] args) {
		int[] a = {3,5,8,1,6,2,0,7,4,9,-1,2};
		mergeSort(a,0,a.length-1);
		printArray(a);
	}
	public static void mergeSort (int[] a, int low, int high) {
		int mid = (high+low)/2;
		if (low<high) {
			mergeSort(a, low, mid);
			mergeSort(a, mid+1, high);
			marge(a, low, mid, high);
		}
	}
	
	/**
	 * 将两个有序数组合并为一个有序数组
	 * a,b合并到c
	 */
	public static void marge(int[] a,int low, int mid, int high) {
		int[] temp = new int[high-low+1];
		int i=low;
		int j=mid+1;
		int k=0;
		for (; i<=mid && j<=high;k++) {
			if (a[i]<a[j]) {
				temp[k] = a[i++]; 
			} else {
				temp[k] = a[j++]; 
			}
		}
		for (;i<=mid;i++,k++) {
			temp[k] = a[i]; 
		}
		for (;j<=high;j++,k++) {
			temp[k] = a[j]; 
		}
		for (int z=0; z<temp.length; z++) {
			a[z+low]=temp[z]; 
		}
	}
	/**
	 * 打印输出数组a到控制台
	 * @param a
	 */
	private static void printArray(int[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i]+"\t");
		}
	}
	/**
	 * 交换数组中两个位置的值
	 * @param a
	 * @param i
	 * @param index
	 */
	private static void swap(int[] a, int i, int index) {
		int temp = 0;
		temp = a[i];
		a[i] = a[index];
		a[index] = temp;
	}
	

}
